// https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
// https://www.bilibili.com/video/BV1YA411v7zF?from=search&seid=1913100809334669630

/**
不断的【两两交换】得到每一次序列

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
*/

class Solution
{
public:
  vector<vector<int>> permute(vector<int> &nums)
  {
    // 最终返回的序列
    vector<vector<int>> result;

    // 递归
    backtrack(
      result,           // 最终的【输出】序列（二维数组）
      nums,             // 传入的【输入】序列: [1,2,3]
      0,                // 从第0个元素开始
      (int)nums.size()  // 原始序列的长度
    );

    return result;
  }

  // - 1,2,3,4,5
  // - 2,1,3,4,5
  //  - 2,1,4,3,5
  //  - 2,1,4,5,3
  //  - 2,1,3,5,4
  //  - 2,1,……
  void backtrack(vector<vector<int>> &result, vector<int> &nums, int index, int len)
  {
    // 当没有可以被交换的序列时停止，当前的序列就是一种全排列，直接保存
    if (index == len)
    {
      result.emplace_back(nums); // 插入【右值】拷贝，因为原始数组已经被修改
      return;
    }

    //
    for (int i = index; i < len; ++i)
    {
      // 交换
      swap(nums[i], nums[index]);

      // 继续递归填下一个数
      backtrack(
        result,
        nums,
        index + 1, // 重要：递归传入 index + 1 下一个元素的位置
        len
      );

      // 还原交换
      swap(nums[i], nums[index]);
    }
  }
};